package com.ljy.my_study.leetcode.对称二叉树;

import java.util.ArrayList;
import java.util.List;

import com.ljy.my_study.lintcode.二叉树的序列化和反序列化.TestMain.TreeNode;

/**
 * @author James
 * @date 2018年9月21日
 */
public class TestMain {
	// 给定一个二叉树，检查它是否是镜像对称的。
	//
	// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
	//
	// 1
	// / \
	// 2 2
	// / \ / \
	// 3 4 4 3
	// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
	//
	// 1
	// / \
	// 2 2
	// \ \
	// 3 3
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		TreeNode treeNode=testMain.deserialize("1,2,2,#,3,3");
		System.out.println(testMain.isSymmetric(treeNode));
	}

	public boolean isSymmetric(TreeNode root) {
		if(root==null) {
			return true;
		}
		List<TreeNode> list=new ArrayList<>();
		list.add(root.left);
		list.add(root.right);
		return isSymmetric(list);
	}
	
	private boolean isSymmetric(List<TreeNode> list) {
		int len=list.size();
		List<TreeNode> newList=new ArrayList<>();
		boolean isAllNotNull=false;
		for(int i=0;i<len/2;i++) {
			if(list.get(i)!=null&&list.get(len-1-i)!=null) {
				if(list.get(i).val!=list.get(len-1-i).val) {
					return false;
				}
				isAllNotNull=true;
			}else if(!(list.get(i)==null&&list.get(len-1-i)==null)) {
				return false;
			}
		}
		if(!isAllNotNull) {
			return true;
		}
		for(int i=0;i<list.size();i++) {
			if(list.get(i)==null) {
				newList.add(null);
			}else {
				if(list.get(i).left==null&&list.get(i).right==null) {
					newList.add(null);
				}else {
					newList.add(list.get(i).left);
					newList.add(list.get(i).right);
				}
			}
		}
		return isSymmetric(newList);
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\"} ";
		}
		
	}
	
	public TreeNode deserialize(String data) {
		if(data==null||data.isEmpty()) {
			return null;
		}
		String[] arrStr=data.split(",");
		TreeNode root=null;
		TreeNode[] treeNodeArr=new TreeNode[arrStr.length];
		for(int i=0;i<arrStr.length;i++) {
			if(!arrStr[i].equals("#")) {
				Integer intVal=Integer.valueOf(arrStr[i]);
				TreeNode thisNode=new TreeNode(intVal);
				if(i==0) {
					root=thisNode;
				}
				treeNodeArr[i]=thisNode;
				if(i%2==0) {
					if(i/2-1>=0) {
						if(treeNodeArr[i/2-1]!=null) {
							treeNodeArr[i/2-1].right=thisNode;
						}
					}
				}else {
					if((i+1)/2-1>=0) {
						if(treeNodeArr[(i+1)/2-1]!=null) {
							treeNodeArr[(i+1)/2-1].left=thisNode;
						}
					}
				}
			}
		}
		return root;
	}
}
